"""
链表
给定两个链表，表示两个非负整数。这些数字按逆序存储，且它们的每个节点都只包含一位数字。将这两个数字相加，并以链表形式返回结果。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8

思路：
题目的大意是两个链表求和，和也是一个链表（链表是逆序存的数字）
这和大数的加减很像，不过这个进位是从后向前。
所以可以同时从前往后加，然后保留进位。

其实做这种大数加减的题目不管是用的大数组还是链表，都是一样的：

首先做个大循环，对每一位进行操作：

当前位：(A[i]+B[i])%10
进位：（A[i]+B[i]）/10
这里要注意一点，就是可能两个数组不是同样的长度，需要考虑一个数组已经到头，另一个数组还没结束的情况
"""


class ListNode:
    # 初始化ListNode类
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    # 添加两个数字的链表表示
    def add_two_numbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 创建一个虚拟头节点，便于处理结果链表
        dummy_head = ListNode(0)
        # 当前指针，用于构建结果链表
        current = dummy_head
        # 进位值，初始为0
        carry = 0

        # 同时遍历两个链表 , 直到其中一个链表遍历完
        while l1 or l2:
            # 获取当前节点的值，如果链表已遍历完，则默认为0
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            # 计算当前位的和及进位
            total = x + y + carry
            carry = total // 10
            # 创建新节点并连接到结果链表
            current.next = ListNode(total % 10)
            # 移动到结果链表的下一个节点
            current = current.next

            # 如果l1链表未遍历完，移动到下一个节点
            if l1:
                l1 = l1.next
            # 如果l2链表未遍历完，移动到下一个节点
            if l2:
                l2 = l2.next

        # 最后如果还有进位,也要添加一个节点
        if carry > 0:
            current.next = ListNode(carry)

        # 返回结果链表，跳过虚拟头节点
        return dummy_head.next


def create_linked_list(values):
    # 根据给定的值列表创建链表
    if not values:
        return None
    # 创建头节点
    head = ListNode(values[0])
    current = head
    # 遍历值列表，创建链表节点
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def print_linked_list(node):
    # 打印链表
    result = []
    while node:
        result.append(str(node.val))
        node = node.next
    print(" -> ".join(result))



if __name__ == '__main__':
    solution = Solution()
    l1 = create_linked_list([2, 4, 3])
    l2 = create_linked_list([5, 6, 4])
    result = solution.add_two_numbers(l1, l2)
    print_linked_list(result)
